#合并两个有序数组
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        a = m - 1
        b = n - 1
        c = -1
        while b >= 0:
            if nums1[a] > nums2[b]:
                nums1[c] = nums1[a]
                nums1[a] = 0
                a = a - 1
                c = c - 1
            else:
                nums1[c] = nums2[b]
                b = b - 1
                c = c - 1



#移除元素
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = len(nums)-1
        while i >= 0:
            if nums[i] == val:
                nums.pop()
            else:
                j = 0
                while j < i:
                    if nums[j] != val:
                        j += 1
                    else:
                        nums[j] = nums[i]
                        nums[i] = val
                        nums.pop()
                        i = i - 1
            i -= 1



#删除有序数组中的重复项
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        j = 1
        while j < len(nums):
            if nums[i] == nums[j]:
                del nums[j]
            else:
                i += 1
                j += 1
        print(len(nums))


#多数元素
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        num = 0
        for i in range(len(nums)):
            if num == 0:
                a = nums[i]
            if nums[i] == a:
                num = num + 1
            else:
                num = num - 1
        return a




#买卖股票的最佳时机
class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        mon = 0
        for i in range(len(prices)-1):
            for j in range(i+1, len(prices)):
                p = prices[j] - prices[i]
                if p > mon:
                    mon = p
        return mon


#最后一个单词的长度
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s = s.rstrip()
        list = s.split(" ")
        return len(list[-1])


#最长公共前缀
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        str0 = min(strs)
        str1 = max(strs)

        for i in range(len(str0)):
            if str0[i] != str1[i]:
                return str0[:i]
        return str0


#找出字符串中第一个匹配项的下标
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack)-len(needle)):
            if haystack[i:i+len(needle)] == needle:
                return i
        else:
            return -1


#验证回文串
class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        list = []
        for i in s:
            if i.isalnum():
                list.append(i)
        list1 = list.copy()
        list2 = list.copy()
        list2.reverse()
        for j in range(len(list)):
            if list1[j] != list2[j]:
                return False
        else:
            return True

#判断子序列
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        j = 0
        for i in s:
            while j < len(t):
                if i != t[j]:
                    j = j + 1
                    continue
                elif i == t[j]:
                    j = j + 1
                    break
            else:
                return False
        else:
            return  True


